package main

import (
	"fmt"
	. "local/algorithm/util"
)

/*
*
A B C D E
C B A D E

第一步圈定要翻转的范围
第二步执行翻转
![](http://cdn.bsummer.cn/20191204123134.png)
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
	node := head
	for i := 0; i < k; i++ {
		if node == nil {
			return head
		}
		node = node.Next
	}
	newhead := reverse(head, node)
	head.Next = reverseKGroup(node, k) //这一步容易出错
	return newhead
}

func reverse(first, last *ListNode) *ListNode {
	prev := last
	for first != last {
		tmp := first.Next
		first.Next = prev
		prev = first
		first = tmp
	}

	return prev
}

func main() {
	list := GenerateLinkedList([]int{1, 2, 3, 4})
	newList := reverseKGroup(list, 3)
	fmt.Println(newList)
}
